package backtracking.other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 51. N 皇后
 * <p>
 * n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 */
public class N51_NQueens {
    private List<List<String>> res = new LinkedList<>();
    char[][] chessboard;

    private void backtracking(int row, int n) {
        if (row == n) { // 当前行等于n 存放结果并放回
            res.add(chessboardToList());
            return;
        }
        for (int i = 0; i < n; i++) {   // 当前行的最左一列开始遍历
            if (isValid(row, i, n)) {   // 放到当前位置是否合法
                chessboard[row][i] = 'Q';   // 放入
                backtracking(row + 1, n);   // 放下一行
                chessboard[row][i] = '.';   // 拿起
            }
        }
    }

    private List<String> chessboardToList() {   // 把棋盘转为字符串列表
        List<String> list = new ArrayList<>();
        for (char[] c : chessboard)
            list.add(String.copyValueOf(c));
        return list;
    }

    private boolean isValid(int row, int col, int n) {
        // 检查列
        for (int i = 0; i < row; i++)
            if (chessboard[i][col] == 'Q') return false;
        // 检查45度
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
            if (chessboard[i][j] == 'Q') return false;
        // 检查135度
        for (int i = row - 1, j = 0; i >= 0 && j <= n - 1; i--, j++)
            if (chessboard[i][j] == 'Q') return false;
        return true;
    }

    public List<List<String>> solveNQueens(int n) {
        chessboard = new char[n][n];
        for (char[] c : chessboard)
            Arrays.fill(c, '.');
        backtracking(0, n);
        return res;
    }
}
